package com.coderside.fragment.arithmetic.packchars;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test2 {

	public List<byte[]> maxLenRepeat(byte[] textBytes) {
		KV kv = leastChar(textBytes);
		int repeatNum = Integer.parseInt(kv.getValue().toString());
		List<byte[]> byteList = null;
		if (repeatNum == 1) {
			
		}
		if (repeatNum > 1) {
			List<Distance> dis = closestChar(textBytes, kv);
			if (dis.size() == 1) {
				Distance d = dis.get(0);
				byteList = caseOne(textBytes, d);
			} else {

			}
		}

		return byteList;
	}

	/**
	 * ���ָ�����ַ��ҳ��ַ���������ٵ�һ���ַ� ���ظ��ַ��byte���͵�ֵ �Լ������˶��ٴ�
	 * @param charsBytes
	 * @return
	 */
	private KV leastChar(byte[] charsBytes) {
		int[] hexCount = new int[16];
		for (int i = 0; i < charsBytes.length; i++) {
			char c = (char) charsBytes[i];
			int index = Integer.parseInt(String.valueOf(c), 16);
			hexCount[index] = ++hexCount[index];
		}
		int min = hexCount[0];
		int minIndex = 0;
		for (int i = 1; i < hexCount.length; i++) {
			if (hexCount[i] < min) {
				min = hexCount[i];
				minIndex = i;
			}
		}
		byte minByte = ("" + minIndex).getBytes()[0];
		System.out.println(minByte);
		KV kv = new KV(minByte, min);
		return kv;
	}

	/**
	 * ��֪�����ַ���ַ������ٵĳ��ֵ��ַ�
	 * �ҳ������ַ��������һ����߶���
	 * @param charsBytes
	 * @param kv
	 * @return
	 */
	private List<Distance> closestChar(byte[] charsBytes, KV kv) {
		int repeatNum = Integer.parseInt(kv.getValue().toString());
		int count = 0;
		int[] minChars = new int[repeatNum];
		//		�����ַ����ҵ��������}��  ����Ҫ��}�����������Ĳ�ֹһ�� ��ֻ��һ��
		for (int i = 0; i < charsBytes.length; i++) {
			Byte b = (Byte) kv.getKey();
			if (b.byteValue() == charsBytes[i]) {
				minChars[count++] = i;
			}
		}

		List<Distance> distanceList = new ArrayList<Distance>();
		for (int i = 0; i < minChars.length - 1; i++) {
			int temp = minChars[i + 1] - minChars[i];
			Distance d = new Distance(temp, minChars[i], minChars[i + 1]);
			distanceList.add(d);
		}
		Collections.sort(distanceList, new Comparator<Distance>() {
			public int compare(Distance o1, Distance o2) {
				if (o1.getSpace() > o2.getSpace()) {
					return 1;
				} else if (o1.getSpace() < o2.getSpace()) {
					return -1;
				}
				return 0;
			}
		});
		Distance top = distanceList.get(0);
		List<Distance> results = new ArrayList<Distance>();
		results.add(top);
		for (int i = 1; i < distanceList.size(); i++) {
			if (top.getSpace() == distanceList.get(i).getSpace()) {
				results.add(distanceList.get(i));
			}
		}
		return results;
	}

	private List<byte[]> caseOne(byte[] bytes, Distance d) {
		//�������ֻ��һ�� 
		//���������ַ�ĶԳƵ��ҳ���ܳ�����ַ���м�λ��
		Prosessor p = getMidPoint(d, bytes.length);
		List<byte[]> byteList = p.handler(bytes);
		byte[] a = new byte[d.getStart()];
		System.arraycopy(bytes, 0, a, 0, a.length);
		byteList.addAll(maxLenRepeat(a));
		byte[] b = new byte[d.getSpace()];
		System.arraycopy(bytes, d.getStart(), b, 0, b.length);
		byteList.addAll(maxLenRepeat(b));
		byte[] c = new byte[bytes.length - d.getEnd()];
		System.arraycopy(bytes, d.getEnd(), c, 0, c.length);
		byteList.addAll(maxLenRepeat(c));
		return byteList;
	}

	private void comparator(byte[] part1, byte[] part2, Distance d) {
		int maxNum = 0;
		byte[] minPart, maxPart;
		if (part1.length >= part2.length) {
			maxNum = part2.length;
			minPart = part2;
			maxPart = part1;
		} else {
			maxNum = part1.length;
			minPart = part1;
			maxPart = part2;
		}
		byte[] repeatBytes = new byte[maxNum];
		int start = d.getStart();
		int desc = start, asc = start;
		repeatBytes[start] = minPart[start];

		while (desc > 0 && asc < maxNum) {
			if (minPart[desc] == maxPart[desc]) {
				repeatBytes[desc] = minPart[desc];
			}
			if (minPart[asc] == maxPart[asc]) {
				repeatBytes[asc] = maxPart[asc];
			}
			desc--;
			asc++;
		}
		System.out.println(repeatBytes);
	}

	/**
	 * �������ľ���Ϳ�ʼ�±��Լ������±껹������ַ�ĳ���
	 * �ҳ���ܳ�����ַ���м�λ��
	 * @param d
	 * @param len
	 * @return
	 */
	private Prosessor getMidPoint(Distance d, int len) {
		int one = d.getStart();
		int two = d.space;
		int three = len - d.getEnd();
		int midPoint = 0;
		Prosessor p = null;
		if (one < two && one < three) {
			//����һ����� end - one ����Ϊ�м��
			midPoint = d.end - one;
			KV p1 = new KV(0, midPoint);
			KV p2 = new KV(midPoint, len);
			Map<KV, KV> map = new HashMap<KV, KV>();
			map.put(p1, p2);
			p = new Prosessor(d, map);
		} else if (two < three && two < one) {
			//���ڶ������ ��ǰƫ��two�±� �������ƫ��two�±�
			Map<KV, KV> map = new HashMap<KV, KV>();
			KV p1 = new KV(d.start - two + 1, d.start);
			KV p2 = new KV(d.start + 1, d.getEnd());
			map.put(p1, p2);
			KV p3 = new KV(d.start, d.start + two - 1);
			KV p4 = new KV(d.start + two, d.getEnd() + two - 1);
			map.put(p3, p4);
			p = new Prosessor(d, map);
		} else if (one == three && one < two) {
			midPoint = d.start + two / 2;
		} else if (one == two && one < three) {
			midPoint = d.start;
		} else {
			midPoint = d.start - three;
		}
		return p;
	}

	public ArrayList QfindChr(String str, String Sfind) {
		int str_length = 0;
		int fin_length = 0;

		int find_count = 0;
		int start = 0;
		int moveNum = 0;
		ArrayList<Integer> index = new ArrayList<Integer>();

		if (Sfind.length() == 0 || str.length() == 0) {
			return null;
		}

		if (str.length() < Sfind.length()) {
			return null;
		}

		str_length = str.length();
		fin_length = Sfind.length();

		while (start + fin_length <= str_length) {
			moveNum++;
			boolean isfind = false;// �Ƿ�������ƶ����ҵ�
			String s_temp = str.substring(start, start + fin_length);
			if (Sfind.equals(s_temp)) {
				index.add(start);// ��¼ƥ���ַ��λ�õĵ�һ���ַ����
				find_count++;
				start = start + fin_length;
				isfind = true;
			}
			if (isfind == false)// ���û�ҵ������´��ƶ�λ��
			{
				int forwardPos = QfindPos(str, Sfind, start, fin_length);
				start = forwardPos;
			}
		}
		System.out.println("move_count = " + moveNum);// �ƶ������������
		return index;
	}

	// ���ַ����ַ�(�������һ���ַ�)��λ��(����)
	// û�ҵ�����fin_length,�ҵ�����λ��
	// / ���ַ����ַ�(�������һ���ַ�)��λ��(����);û�ҵ�����str.length,�ҵ�����λ��
	public int QfindPos(String str, String find, int pos, int fin_length) {
		int returnPos = str.length();
		char[] Schr = str.toCharArray();
		char[] Sfin = find.toCharArray();

		if ((pos + fin_length) < str.length()) {
			char chrFind = Schr[pos + fin_length];// Ҫ�ҵ��ַ�
			if (fin_length >= 1) {
				if (find.lastIndexOf(chrFind) > -1)// ���find�����chrFind�ַ�
				{
					returnPos = pos + fin_length - find.lastIndexOf(chrFind);
				} else {// ���find�ﲻ����chrFind�ַ�
					returnPos = pos + fin_length + 1;
				}
			}
		}
		return returnPos;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//�ҵ��ַ����ַ������ٵ��ַ�
		String ss = "��Ϊ���ز�����Ĺ�̵��У�һ�����αȽ��٣���õ��ز����¶ȱȽϸߵ�����·ŵ�ʱ��һ�����������ϸ��ͻ����ֳ����������ϸ��������»ᱻ��ԭ���������Ρ�������������Ȼ�缫���밷�ϳ������������ǿ�°��������ǳ���ʳ��ʣ���߲ˣ������ǵĽ����ǲ���ģ�������ʳ������̲�֮���ʳƷ��θ���ļ��ʾͱȽϸ�";
		String text = HexUtils.convert(ss.getBytes());
		byte[] bs = text.getBytes();
		Test2 t = new Test2();
		t.maxLenRepeat(bs);
		//		�ҳ���ܳ���������м�λ��
		//		���м�λ�÷ָ��}�� ���������ַ��ظ�����}�������ҳ���}��ο��ܳ��ֵ��ظ���

		//		�����ҳ��4���ظ����������ļ�����}�������ַ�س�����в������

	}

}
